#pragma once
#include <iostream>
#include <vector>
#include <string>
using namespace std;

class Solution {
	string numToStr[10] = { "", "", "abc", "def", "ghi", "jkl", "mno",
		"pqrs", "tuv", "wxyz" };
public:
	void Combinations(const string& digits, size_t di, string combinestr, vector<string>& strV)
	{
		if (di == digits.size())
		{
			strV.push_back(combinestr);
			return;
		}
		int num = digits[di] - '0';
		string str = numToStr[num];
		for (auto ch : str)
		{
			Combinations(digits, di + 1, combinestr + ch, strV);
		}
	}

	vector<string> letterCombinations(string digits) {
		vector<string> strV;
		if (digits.size() == 0)
		{
			return strV;
		}
		Combinations(digits, 0, "", strV);
		return strV;
	}
};